1. Field of the Invention
Embodiments of the invention relate to a nonvolatile memory. More particularly, embodiments of the invention relate to a method of mapping a nonvolatile memory based on a map history and a storage device of performing the method.
2. Description of the Related Art
Semiconductor memories may be generally divided into volatile memories and non-volatile memories. Volatile memories, e.g., a dynamic random access memory (DRAM) and a static random access memory (SRAM), lose data stored therein when power is turned off. Non-volatile memories keep stored data over time, even when power is turned off. An electrically erasable programmable read only memory (EEPROM) capable of electrically writing/reading data has been widely developed as a non-volatile memory.
Operation modes of EEPROMs may be divided into a write mode or a program mode, during which a threshold voltage of a memory cell is programmed, a read mode during which data stored in the memory cell is read out and an erase mode during which the memory cell is initialized by erasing the stored data.
A flash memory may be an advanced type device of the EEPROM. The flash memory performs an erase operation by block units and performs a program operation by page units. Each page includes all or a portion of memory cells commonly coupled to a word line. Flash memories may be classified as a NAND type flash memory or a NOR type flash memory based on an arrangement of a memory cell array. NAND type flash memories may include cell transistors that are connected in series between a bit line and a ground line. NOR type flash memories may include cell transistors that are connected in parallel between the bit line and the ground line. NAND type flash memories cannot access the memory cell array in byte units during a read operation or a program operation. However, the NAND type flash memory may more rapidly program and more rapidly erase the memory cell array.
A non-volatile memory performs an erase operation and an access operation (that is, a write operation and a read operation) based on different units. The non-volatile memory has a limitation such that the non-volatile memory cannot perform the erase operation or the write operation above a predetermined number of times. To overcome such a limitation on the number of the operations, an intermediate process is employed to efficiently map logical addresses, which are generated by a file system of a host such as a personal computer, to physical addresses of the non-volatile memory. For example, a flash translation layer (FTL) implemented as an intermediary may be coupled between a host using a file system for a hard disk and a flash memory for efficiently mapping the logical addresses to the physical addresses.
However, mapping information between the logical addresses and the physical addresses may be scattered in the non-volatile memory. The scattered mapping information may be implemented as a map table during initialization of the non-volatile memory to increase an access speed of the non-volatile memory.
Since valid map units are scattered over map blocks, all of used map blocks must be fully scanned in sequence to update a map table by identifying locations of currently valid map units. During a map opening operation (that is, when the map table is constructed while a memory is initialized), the used and recently allocated map blocks are read in order to construct the map table.
For example, if the non-volatile memory includes m used map blocks and one recently allocated map block, where each of the map blocks has n pages and a scan time is tR per page, a time period for constructing the map table is (m+1)*n*tR.
Since valid map units are searched by scanning all of the used map blocks to construct the map table, a search time for constructing the map block increases as the used map blocks increases. As a density of a memory device increases, the number of the map blocks included in the non-volatile memory increases and the number of pages included in each of the map blocks increases. Accordingly, a map open time increases considerably.
Therefore, a storage device including such a non-volatile memory has a long initialization time because of increased time for constructing the map table when a number of map blocks exist. Such an increase in the initialization time may deteriorate performances of the storage device and a system including the storage device. In this case, some regular requirements, such as a host open time specification, may not be satisfied.